Optimal Unlabeled Set Partitioning with Application to Risk-based Quarantine Policies

We consider the problem of partitioning a set of items into unlabeled subsets so as to optimize an additive objective, i.e., the objective function value of a partition is equal to the sum of the contribution of each subset. Under an arbitrary objective function, this family of problems is known to be an N P -complete combinatorial optimization problem. We study this problem under a broad family of objective functions characterized by elementary symmetric polynomials, which are "building blocks” to symmetric functions. By analyzing a continuous relaxation of the problem, we identify conditions that enable the use of a reformulation technique in which the set partitioning problem is cast as a more tractable network flow problem solvable in polynomial-time. We show that a number of results from the literature arise as special cases of our proposed framework, highlighting its generality. We demonstrate the usefulness of the developed methodology through a novel and timely application of quarantining heterogeneous populations in an optimal manner. Our case study on real COVID-19 data reveals significant benefits over conventional measures in terms of both spread mitigation and economic impact, underscoring the importance of data-driven policies. [ FROM AUTHOR] Copyright of IISE Transactions is the property of Taylor & Francis Ltd and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full . (Copyright applies to all s.)

An Optimization-based Framework to Minimize the Spread of Diseases in Social Networks with Heterogeneous Nodes

We provide an optimization-based framework that identifies social separation policies to mitigate the spread of diseases in social networks. The study considers subject-specific risk information, social structure, and the negative economic impact of imposing restrictions. We first analyze a simplified variation of the problem consisting of a single period and a specific social structure to establish key structural properties and construct a tailored globally-convergent solution scheme. We extend this solution scheme to heuristically solve the more general model with multiple time periods and any social structure. We use real COVID-19 data to illustrate the benefits of proposed framework. Our results reveal that the optimized policies substantially reduce the spread of the disease when compared to existing benchmark algorithms and policies that are based on a single risk factor. In addition, we utilize the considered framework to identify important subject attributes when distributing Personal Protective Equipment (PPE). Moreover, results reveal that the optimized policies continue to outperform under a more realistic setting. Our results underscore the importance of considering subject-specific information when designing policies and provide high-level data-driven observations to policy-makers that are tailored to the specific risk profile of the population that is being served. [ FROM AUTHOR] Copyright of IISE Transactions is the property of Taylor & Francis Ltd and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full . (Copyright applies to all s.)

Screening multi-dimensional heterogeneous populations for infectious diseases under scarce testing resources, with application to COVID-19

Abstract Testing provides essential information for managing infectious disease outbreaks, such as the COVID-19 pandemic. When testing resources are scarce, an important managerial decision is who to test. This decision is compounded by the fact that potential testing subjects are heterogeneous in multiple dimensions that are important to consider, including their likelihood of being disease-positive, and how much potential harm would be averted through testing and the subsequent interventions. To increase testing coverage, pooled testing can be utilized, but this comes at a cost of increased false-negatives when the test is imperfect. Then, the decision problem is to partition the heterogeneous testing population into three mutually exclusive sets: those to be individually tested, those to be pool tested, and those not to be tested. Additionally, the subjects to be pool tested must be further partitioned into testing pools, potentially containing different numbers of subjects. The objectives include the minimization of harm (through detection and mitigation) or maximization of testing coverage. We develop data-driven optimization models and algorithms to design pooled testing strategies, and show, via a COVID-19 contact tracing case study, that the proposed testing strategies can substantially outperform the current practice used for COVID-19 contact tracing (individually testing those contacts with symptoms). Our results demonstrate the substantial benefits of optimizing the testing design, while considering the multiple dimensions of population heterogeneity and the limited testing capacity.

A robust pooled testing approach to expand COVID-19 screening capacity.

Limited testing capacity for COVID-19 has hampered the pandemic response. Pooling is a testing method wherein samples from specimens (e.g., swabs) from multiple subjects are combined into a pool and screened with a single test. If the pool tests positive, then new samples from the collected specimens are individually tested, while if the pool tests negative, the subjects are classified as negative for the disease. Pooling can substantially expand COVID-19 testing capacity and throughput, without requiring additional resources. We develop a mathematical model to determine the best pool size for different risk groups, based on each group's estimated COVID-19 prevalence. Our approach takes into consideration the sensitivity and specificity of the test, and a dynamic and uncertain prevalence, and provides a robust pool size for each group. For practical relevance, we also develop a companion COVID-19 pooling design tool (through a spread sheet). To demonstrate the potential value of pooling, we study COVID-19 screening using testing data from Iceland for the period, February-28-2020 to June-14-2020, for subjects stratified into high- and low-risk groups. We implement the robust pooling strategy within a sequential framework, which updates pool sizes each week, for each risk group, based on prior week's testing data. Robust pooling reduces the number of tests, over individual testing, by 88.5% to 90.2%, and 54.2% to 61.9%, respectively, for the low-risk and high-risk groups (based on test sensitivity values in the range [0.71, 0.98] as reported in the literature). This results in much shorter times, on average, to get the test results compared to individual testing (due to the higher testing throughput), and also allows for expanded screening to cover more individuals. Thus, robust pooling can potentially be a valuable strategy for COVID-19 screening.